In a mobile communications system, uplink synchronization is required before data can be transmitted in the uplink. In E-UTRA, uplink synchronization of a mobile is initially performed in the random access procedure. The mobile initiates the random access procedure by selecting a random access preamble from a set of allocated preambles in the cell where the mobile is located, and transmitting the selected random access preamble. In the base station, a receiver correlates the received signal with a set of all random access preambles allocated in the cell to determine the transmitted preamble.
The random access preamble sequences in E-UTRA are designed such that the autocorrelation is ideal and such that the cross-correlation between two different preambles is small. These properties enable accurate time estimates needed for the uplink synchronization and good detection properties of the preambles. These random access preamble sequences in E-UTRA are derived from Zadoff-Chu sequences of odd length. Zadoff-Chu sequences pu,q(n) of length N, where N is odd, are defined as (see [1]):
                                                                        p                                  u                  ,                  q                                            ⁡                              (                n                )                                      =                          W                                                                    un                    ⁡                                          (                                              n                        +                        1                                            )                                                        /                  2                                +                qn                                              ,                                          ⁢                      n            =            0                    ,          1          ,          …          ⁢                                          ,                                    N              -              1                        ;                          ⁢                                  ⁢                  W          =                      ⅇ                                          -                j2π                            N                                                          (        1        )            where the integers u and N are relatively prime, i.e. the greatest common divisor of u and N is 1. Furthermore, q is an arbitrary integer and j is the imaginary unit. The random access preambles in E-UTRA are defined in time domain as cyclic shifts of Zadoff-Chu root sequences of odd length with q=0 (see [2]):pu(n)=pu,0(n)=Wun(n+1)/2, n=0,1, . . . ,N−1  (2)
The random access preamble in E-UTRA contains a cyclic prefix, which makes it advantageous to perform the correlation of the received signal with the random access preambles in the frequency domain. The structure of a random access preamble receiver in a base station is shown in FIG. 1.
In FIG. 1 a received signal is forwarded to a block 10 for removing the cyclic prefix (CP). The remaining signal is subjected to a Discrete Fourier Transform (DFT) in block 12. The obtained discrete Fourier transform is forwarded to a set of correlators 14, where it is multiplied element-wise by a set of DFTs of preamble sequences indexed by umin . . . umax and generated by blocks 16. The products are subjected to an Inverse Discrete Fourier Transform (IDFT) in blocks 18. The correlator output signals are then forwarded to a corresponding set of detectors 20, which determine the generated preamble that best matches the received signal.
The preambles used for uplink synchronization are also generated in the mobile stations. Another application of Zadoff-Chu sequences is generation of mobile station reference signal sequences transmitted on the uplink. In contrast to the random access preambles, which are defined in time domain, the reference signals in E-UTRA are defined in frequency domain by (2) together with truncation of the Zadoff-Chu sequence, i.e. some samples at the end of the sequence are not included in the reference signal.
The exponent un(n+1)/2+qn in the definition of the Zadoff-Chu sequence is always an integer because either n or n+1 is even and so one of them must be divisible by 2. Furthermore, since u, q and n are all integers, the exponent must be an integer as well. Since the function Wm is periodic in m with period N and all entities in the exponent are integers, all arithmetic can be performed modulo N in the exponent un(n+1)/2+qn.
Division modulo N differs from ordinary division and involves the inverse modulo N. The inverse of b modulo N is defined as the integer such that 0<b−1<N and bb−1=1 mod N. The inverse modulo N of b exists if and only if b and N are relatively prime. If N is prime b−1 exists for all b≠mod N. Division of a by b modulo N is accomplished by multiplying a by the inverse modulo N of b:ab−1.
Performing the arithmetic modulo N in the exponent gives an alternative and useful expression of the Zadoff-Chu sequence:pu,q(n)=Wun(n+1)·2−1qn,n=0,1, . . . ,N−1  (3)
Note that with the notation used for modulo N arithmetic, 2−1 is not the same as ½. Instead it denotes the inverse modulo N of 2 (which depends on N).
It has been shown (see [3]) that the DFT of pu(n) is given by:Pu(k)=W−k(k+u)·2−1u−1Σn=0N-1pu((n+u−1k)mod N)  (4)
Since the sum in (4) is always over all elements of pu(n), the sum is independent of k, thus:Pu(k)=AuW−k(k+u)·2−1u−1  (5)where Au is independent of k. From Parseval's theorem one can show (see [4]) that |Au|=√{square root over (N)} for any value of u and thus Au=√{square root over (N)}ejφu, where ejφu is a constant complex phase factor.
Comparing (3) and (5) it is clear that the DFT of the Zadoff-Chu sequence is itself a Zadoff-Chu sequence multiplied by a constant:Pu(k)=AuW−k(k+u)·2−1u−1=Aup−u−1, q(k), q=(u−1−1)·2−1  (6)
In each correlator 14 in FIG. 1, the received signal is multiplied element-wise with the DFT of a preamble in the cell.
In a straightforward generator of the DFT of the preamble, the exponent a(k)=−k(k+u)·2−1u−1 in (6) is calculated for every value of k and the values of Wa(k) are either calculated or read from a table. The detectors 20 only need the absolute values of the respective correlator outputs, so only the absolute value of Au is relevant. Since the absolute value, |Au|=√{square root over (N)} for any value of u, Au can be completely discarded in the correlators. Thus, for the purpose of correlation the preamble may be represented by a Zadoff-Chu sequence both in the time and frequency domain, which implies that a representation of the DFT of the preamble may be generated directly in the frequency domain as a Zadoff-Chu sequence.
The sequence generation in existing technology requires two multiplications to calculate the exponent a(k)=−k(k+u)·2−1u−1 in (6) for every sample in the sequence. The total computational complexity of these multiplications may be significant for long sequences. For instance, the length of the random access preamble in E-UTRA is N=839 for most preamble formats, and in a worst case the receiver needs to correlate the received signal with as many as 64 different Zadoff-Chu sequences (this corresponds to 64 blocks 16 in FIG. 1).
Document [6] describes modulation of a Zadoff-Chu sequence with at least two modulation sequences for deriving a Generalized Chirp-Like (GCL) sequences used for correlation with an input signal.
Document [7] discusses Zadoff-Chu sequence allocation allowing efficient matched filter implementation for frequency domain and time domain RACH preamble detection.